/*
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
*/
const findAnagrams = function (s, p) {
  const window = new Map()
  const needs = new Map()
  for (let i of p) needs.set(i, (needs.get(i) || 0) + 1)
  let left = right = 0
  let valid = 0
  const res = []
  while (right < s.length) {
    const c = s[right]
    right++
    if (needs.has(c)) {
      window.set(c, (window.get(c) || 0) + 1)
      if (window.get(c) === needs.get(c)) valid++
    }
    while (right - left >= p.length) {
      if (valid === needs.size) {
        res.push(left)
      }
      const d = s[left]
      left++
      if (needs.has(d)) {
        if (window.get(d) === needs.get(d)) valid--
        window.set(d, window.get(d) - 1)
      }
    }
  }
  return res
}